<DOCTYPE html>
  <html lang="en">

  <head charset="UTF-8">
    <title></title>
  </head>

  <body>
    <script>
      function BinarySearchTree() {
        let root = null
        let length = 0

        function Node(key) {
          let key = key
          let left = null
          let right = null
        }

        //1.添加
        BinarySearchTree.prototype.insert = key => {
          let node = new Node(key);
          if (this.length == 0) {
            this.head = node;
            this.length++;
          } else {
            if (!this.search(key)) {
              let current = this.root;
              this.insertNode(current, key);
              this.length++;
              return
            }
          }
        }

        BinarySearchTree.prototype.insertNode = (current, key) => {
          if (key < current.key) {
            if (current.left == null) {
              key = current.left;
              return
            }
            this.insertNode(current.left);
          } else {
            if (current.right == null) {
              key = current.right;
              return
            }
            this.insertNode(current.right);
          }
        }

        //2.查找
        BinarySearchTree.prototype.search = key => {
          if (this.length == 0) {
            return null
          } else {
            let current = this.root;
            if (this.searchNode(current, key)) {
              return true
            } else {
              return false
            }
          }
        }

        BinarySearchTree.prototype.searchNode = (current, key) => {
          if (key == current) {
            return true
          }
          if (key < current.key) {
            if (current.left == null) {
              return false
            }
            this.searchNode(current.left);
          } else {
            if (current.right == null) {
              return false
            }
            this.searchNode(current.right);
          }
        }

        //3.遍历节点下的所有
        BinarySearchTree.prototype.traverse = key => {
          if (this.length == 0) {
            return null
          } else {
            let result = '';
            result += this.traversalNode(key.left) + ' ';
            result += key + ' ';
            result += this.traversalNode(key.right);
            return result
          }
        }

        BinarySearchTree.prototype.traversalNode = key => {
          let result = ''
          if (key.left != null) {
            result += ' ' + this.traversalNode(key.left) + ' ';
          }
          result += key + ' '
          if (key.right != null) {
            result += this.traversalNode(key.right);
          }
          return result;
        }

        //4.查找最小值最大值
        BinarySearchTree.prototype.min = () => {
          if (this.length == 0) {
            return null
          }
          let current = this.root
          while (current.left != null) {
            current = current.left
          }
          return current
        }

        BinarySearchTree.prototype.max = () => {
          if (this.length == 0) {
            return null
          }
          let current = this.root
          while (current.right != null) {
            current = current.right
          }
          return current
        }

        //查找节点下的最小最大
        BinarySearchTree.prototype.nodeMin = key => {
          while (key.left != null) {
            key = key.left
          }
          return key
        }
        BinarySearchTree.prototype.nodeMax = key => {
          while (key.right != null) {
            key = key.right
          }
          return key
        }
        //5.删除
        BinarySearchTree.prototype.remove = key => {
          if (this.search() != null) {
            if (key == this.root) {
              this.root = null
            } else {
              let previous = this.removePrevious(this.root, key);
              if (key.left == null && key.right == null) {
                previous > key ? previous.left = null : previous.right = null
              } else if (key.left != null && key.right == null) {
                if (previous > key) {
                  let current = this.nodeMax(key.left)
                  current.left = key.left;
                  previous.left = current;
                  let currentPrevious = this.removePrevious(this.root, current);
                  currentPrevious.right = null
                } else {
                  let current = this.nodeMin(key.right)
                  current.right = key.left;
                  previous.right = current;
                  let currentPrevious = this.removePrevious(this.root, current);
                  currentPrevious.left = null
                }
              } else if (key.left == null && key.right != null) {
                if (previous > key) {
                  let current = this.nodeMax(key.right)
                  current.right = key.right;
                  previous.left = current;
                  let currentPrevious = this.removePrevious(this.root, current);
                  currentPrevious.right = null
                } else {
                  let current = this.nodeMin(key.right)
                  current.left = key.right;
                  previous.right = current;
                  let currentPrevious = this.removePrevious(this.root, current);
                  currentPrevious.left = null
                }
              } else {
                if (previous > key) {
                  let current = this.nodeMin(key.right)
                  current.left = key.left;
                  current.right = key.right;
                  previous.left = current;
                  let currentPrevious = this.removePrevious(this.root, current);
                  currentPrevious.left = null
                } else {
                  let current = this.nodeMax(key.left);
                  current.left = key.left;
                  current.right = key.right;
                  previous.right = current;
                  let currentPrevious = this.removePrevious(this.root, current);
                  currentPrevious.right = null
                }
              }
            }
          } else {
            return false
          }
        }

        BinarySearchTree.prototype.removePrevious = (root, key) => {
          if (root.left != key && root.right != key) {
            if (key < root) {
              root = this.removePrevious(root.left, key)
            } else {
              root = this.removePrevious(root.right, key)
            }
            return root
          }
          return root
        }
      }
    </script>
  </body>

  </html>